package com.hdu.hot100.tree;

public class lc543 {


    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    class Solution {
        public int diameterOfBinaryTree(TreeNode root) {
            return f(root).width - 1;
        }

        Info f(TreeNode root)
        {
            if (root == null) return new Info(0, 0);
            Info l = f(root.left);
            Info r = f(root.right);

            int p1 = l.height + r.height + 1;
            int p2 = Math.max(l.width, r.width);

            int curHeight = Math.max(l.height, r.height) + 1;

            return new Info(
                    Math.max(p1, p2),
                    curHeight
            );
        }

        class Info
        {
            int width;
            int height;

            public Info(int width, int height)
            {
                this.width = width;
                this.height = height;
            }
        }
    }
}
